//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。
//
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
//
//
//
// 示例 1：
//
//
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4]
//
// 示例 2：
//
//
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1]
//
// 示例 3：
//
//
//输入：nums = [], target = 0
//输出：[-1,-1]
//
//
//
// 提示：
//
//
// 0 <= nums.length <= 10⁵
// -10⁹ <= nums[i] <= 10⁹
// nums 是一个非递减数组
// -10⁹ <= target <= 10⁹
//
// Related Topics 数组 二分查找 👍 1769 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

class 在排序数组中查找元素的第一个和最后一个位置 {
    public static void main(String[] args) {
        Solution solution = new 在排序数组中查找元素的第一个和最后一个位置().new Solution();
        int[] ans = solution.searchRange(new int[]{1, 2, 3, 3, 4, 5}, 4);
        Arrays.stream(ans).forEach(System.out::println);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] ans = {-1, -1};
            if (nums == null || nums.length == 0) {
                return ans;
            }
            ans[0] = findFirst(nums, target);
            ans[1] = findLast(nums, target);
            return ans;
        }
        //小于等于最左
        public int findFirst(int[] arr, int target) {
            int L = 0;
            int R = arr.length - 1;
            int ans = -1;
            int mid = 0;
            while (L <= R) {
                mid = L + ((R - L) >> 1);
                if (arr[mid] < target) {
                    L = mid + 1;
                } else if (arr[mid] > target) {
                    R = mid - 1;
                } else {
                    ans = mid;
                    R = mid - 1;
                }
            }
            return ans;
        }

        //大于等于最右
        public int findLast(int[] arr, int target) {
            int L = 0;
            int R = arr.length - 1;
            int ans = -1;
            int mid = 0;
            while (L <= R) {
                mid = L + ((R - L) >> 1);
                if (arr[mid] < target) {
                    L = mid + 1;
                } else if (arr[mid] > target) {
                    R = mid - 1;
                } else {
                    ans = mid;
                    L = mid + 1;
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
